from functools import cache
from typing import List

# 记忆化搜索
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:

        n = len(coins)

        @cache
        def dfs(i, cnt):
            # 递归到最后
            if i < 0:
                # 递归到最后 cnt==0 也是一种条件 返回1
                return 1 if cnt == 0 else 0
            # 当前背包 不足以 选第i个硬币
            if cnt < coins[i]:
                return dfs(i - 1, cnt)
            # 不选 + 选
            return dfs(i - 1, cnt) + dfs(i, cnt - coins[i])

        return dfs(n - 1, amount)

